package cn.lintcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 找到子数组的索引,索引范围内和为0
 * [l,r]区间和为0,说明[0,l-1]区间的累加和 == [0,r] 区间的累加和相等
 * 那个[了,r]区间的和一定是0
 * @author labvi
 * @version 1.0.0
 */
public class SubArraySUM {

    public List<Integer> subarraySum(int[] nums) {
        // write your code here
        int len = nums.length;

        ArrayList<Integer> ans = new ArrayList<Integer>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        map.put(0, -1);

        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];

            if (map.containsKey(sum)) {
                ans.add(map.get(sum) + 1);
                ans.add(i);
                return ans;
            }
            map.put(sum, i);
        }

        return ans;
    }

    public static void main(String[] args) {
        SubArraySUM subArraySUM = new SubArraySUM();
        List<Integer> integers = subArraySUM.subarraySum(new int[]{1, 2, 3, 4, 5, -5, 6});
        integers.forEach(System.out::println);
    }
}
